package com.springboot.java.design.sort;

/***
 *  插入排序  时间复杂度O(n^2)
 */
public class InsertSort {

    public static void main(String[] args) {

        int[] arr = new int[]{3,4,6,1,8,2,0};

        // 外层循环代表未排序区间，默认除首元素外的所有元素
        for (int i = 1; i < arr.length; i++) {

            int j = i -1;

            int value = arr[i];

            // 从后向前排
            for (; j >= 0; --j) {
                if(arr[j] > value){
                    // 在已排序区间进行排序
                    arr[j+1] = arr[j];
                }else {
                    // 如果排序完成跳出本循环
                    break;
                }
            }
            // 如果刚好排最后 直接插入
            arr[j+1] = value;
        }

        for (int i : arr) {
            System.out.println(i);
        }


    }

}
